Search results for "Generating Function"
showing 10 items of 24 documents
Is there an absolutely continuous random variable with equal probability density and cumulative distribution functions in its support? Is it unique? …
2014
This paper inquires about the existence and uniqueness of a univariate continuous random variable for which both cumulative distribution and density functions are equal and asks about the conditions under which a possible extrapolation of the solution to the discrete case is possible. The issue is presented and solved as a problem and allows to obtain a new family of probability distributions. The different approaches followed to reach the solution could also serve to warn about some properties of density and cumulative functions that usually go unnoticed, helping to deepen the understanding of some of the weapons of the mathematical statistician’s arsenal.
STURMIAN WORDS AND AMBIGUOUS CONTEXT-FREE LANGUAGES
1990
If x is a rational number, 0<x≤1, then A(x)c is a context-free language, where A(x) is the set of factors of the infinite Sturmian words with asymptotic density of 1’s smaller than or equal to x. We also prove a “gap” theorem i.e. A(x) can never be an unambiguous co-context-free language. The “gap” theorem is established by proving that the counting generating function of A(x) is transcendental. We show some links between Sturmian words, combinatorics and number theory.
General Solution of a Second-Order Nonhomogenous Linear Difference Equation with Noncommutative Coefficients
2010
The detailed construction of the general solution of a second-order nonhomogenous linear operator-difference equation is presented. The wide applicability of such an equation as well as the usefulness of its resolutive formula is shown by studying some applications belonging to different mathematical contexts.
Generalized Schröder permutations
2013
We give the generating function for the integer sequence enumerating a class of pattern avoiding permutations depending on two parameters: m and p. The avoided patterns are the permutations of length m with the largest element in the first position and the second largest in one of the last p positions. For particular instances of m and p we obtain pattern avoiding classes enumerated by Schroder, Catalan and central binomial coefficient numbers, and thus, the obtained two-parameter generating function gathers under one roof known generating functions and expresses new ones. This work generalizes some earlier results of Barcucci et al. (2000) [2], Kremer (2000) [5] and Kremer (2003) [6].
Restricted 123-avoiding Baxter permutations and the Padovan numbers
2007
AbstractBaxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.
Combinatorial aspects of L-convex polyominoes
2007
We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can be connected with an ''L'' shaped path in one of its four cyclic orientations. The paper proves bijectively that the number f"n of L-convex polyominoes with perimeter 2(n+2) satisfies the linear recurrence relation f"n"+"2=4f"n"+"1-2f"n, by first establishing a recurrence of the same form for the cardinality of the ''2-compositions'' of a natural number n, a simple generalization of the ordinary compositions of n. Then, such 2-compositions are studied and bijectively related to certain words of a regular language over four letters which is in turn bijectively related to L-convex polyominoes. In …
Dyck paths with a first return decomposition constrained by height
2018
International audience; We study the enumeration of Dyck paths having a first return decomposition with special properties based on a height constraint. We exhibit new restricted sets of Dyck paths counted by the Motzkin numbers, and we give a constructive bijection between these objects and Motzkin paths. As a byproduct, we provide a generating function for the number of Motzkin paths of height k with a flat (resp. with no flats) at the maximal height. (C) 2018 Elsevier B.V. All rights reserved.KeywordsKeyWords Plus:STATISTICS; STRINGS
Enumeration of L-convex polyominoes by rows and columns
2005
In this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once.Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the rational recurrence relation fn = 4fn-1 - 2fn-2, with f0 = 1, f1 = 2, f2 = 7. Moreover, we give a combinatorial interpretation of this statement. In the last section, we present some open problems.
Right-jumps and pattern avoiding permutations
2015
We study the iteration of the process "a particle jumps to the right" in permutations. We prove that the set of permutations obtained in this model after a given number of iterations from the identity is a class of pattern avoiding permutations. We characterize the elements of the basis of this class and we enumerate these "forbidden minimal patterns" by giving their bivariate exponential generating function: we achieve this via a catalytic variable, the number of left-to-right maxima. We show that this generating function is a D-finite function satisfying a nice differential equation of order~2. We give some congruence properties for the coefficients of this generating function, and we sho…
Descent distribution on Catalan words avoiding a pattern of length at most three
2018
Catalan words are particular growth-restricted words over the set of non-negative integers, and they represent still another combinatorial class counted by the Catalan numbers. We study the distribution of descents on the sets of Catalan words avoiding a pattern of length at most three: for each such a pattern $p$ we provide a bivariate generating function where the coefficient of $x^ny^k$ in its series expansion is the number of length $n$ Catalan words with $k$ descents and avoiding $p$. As a byproduct, we enumerate the set of Catalan words avoiding $p$, and we provide the popularity of descents on this set. Some of the obtained enumerating sequences are not yet recorded in the On-line En…